994. Rotting Oranges
Medium

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

 

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.
Accepted
221,804
Submissions
445,101
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.60 (57 votes)

Premium

Solution


Approach 1: Breadth-First Search (BFS)

Intuition

This is yet another 2D traversal problem. As we know, the common algorithmic strategies to deal with these problems would be Breadth-First Search (BFS) and Depth-First Search (DFS).

As suggested by its name, the BFS strategy prioritizes the breadth over depth, i.e. it goes wider before it goes deeper. On the other hand, the DFS strategy prioritizes the depth over breadth.

The choice of strategy depends on the nature of the problem. Though sometimes, they are both applicable for the same problem. In addition to 2D grids, these two algorithms are often applied to problems associated with tree or graph data structures as well.

In this problem, one can see that BFS would be a better fit.

Because the process of rotting could be explained perfectly with the BFS procedure, i.e. the rotten oranges will contaminate their neighbors first, before the contamination propagates to other fresh oranges that are farther away.

If one is not familiar with the algorithm of BFS, one can refer to our Explore card of Queue & Stack which covers this subject.

However, it would be more intuitive to visualize the rotting process with a graph data structure, where each node represents a cell and the edge between two nodes indicates that the given two cells are adjacent to each other.

Grid to Graph

In the above graph (pun intended), as we can see, starting from the top rotten orange, the contamination would propagate layer by layer (or level by level), until it reaches the farthest fresh oranges. The number of minutes that are elapsed would be equivalent to the number of levels in the graph that we traverse during the propagation.

Current
1 / 5

Algorithm

One of the most distinguished code patterns in BFS algorithms is that often we use a queue data structure to keep track of the candidates that we need to visit during the process.

The main algorithm is built around a loop iterating through the queue. At each iteration, we pop out an element from the head of the queue. Then we do some particular process with the popped element. More importantly, we then append neighbors of the popped element into the queue, to keep the BFS process running.

Here are some sample implementations.

In the above implementations, we applied some tricks to further optimize both the time and space complexities.

  • Usually in BFS algorithms, we keep a visited table which records the visited candidates. The visited table helps us to avoid repetitive visits.

  • But as one notices, rather than using the visited table, we reuse the input grid to keep track of our visits, i.e. we were altering the status of the input grid in-place.

  • This in-place technique reduces the memory consumption of our algorithm. Also, it has a constant time complexity to check the current status (i.e. array access, grid[row][col]), rather than referring to the visited table which might be of constant time complexity as well (e.g. hash table) but in reality could be slower than array access.

  • We use a delimiter (i.e. (row=-1, col=-1)) in the queue to separate cells on different levels. In this way, we only need one queue for the iteration. As an alternative, one can create a queue for each level and alternate between the queues, though technically the initialization and the assignment of each queue could consume some extra time.

Complexity

  • Time Complexity: O(N)\mathcal{O}(N), where NN is the size of the grid.

    First, we scan the grid to find the initial values for the queue, which would take O(N)\mathcal{O}(N) time.

    Then we run the BFS process on the queue, which in the worst case would enumerate all the cells in the grid once and only once. Therefore, it takes O(N)\mathcal{O}(N) time.

    Thus combining the above two steps, the overall time complexity would be O(N)+O(N)=O(N)\mathcal{O}(N) + \mathcal{O}(N) = \mathcal{O}(N)

  • Space Complexity: O(N)\mathcal{O}(N), where NN is the size of the grid.

    In the worst case, the grid is filled with rotten oranges. As a result, the queue would be initialized with all the cells in the grid.

    By the way, normally for BFS, the main space complexity lies in the process rather than the initialization. For instance, for a BFS traversal in a tree, at any given moment, the queue would hold no more than 2 levels of tree nodes. Therefore, the space complexity of BFS traversal in a tree would depend on the width of the input tree.




Approach 2: In-place BFS

Intuition

Although there is no doubt that the best strategy for this problem is BFS, some users in the Discussion forum have proposed different implementations of BFS with constant space complexity O(1)\mathcal{O}(1). To name just a few, one can see the posts from @manky and @votrubac.

As one might recall from the previous BFS implementation, its space complexity is mainly due to the queue that we were using to keep the order for the visits of cells. In order to achieve O(1)\mathcal{O}(1) space complexity, we then need to eliminate the queue in the BFS.

The secret in doing BFS traversal without a queue lies in the technique called in-place algorithm, which transforms input to solve the problem without using auxiliary data structure.

Actually, we have already had a taste of in-place algorithm in the previous implementation of BFS, where we directly modified the input grid to mark the oranges that turn rotten, rather than using an additional visited table.

How about we apply the in-place algorithm again, but this time for the role of the queue variable in our previous BFS implementation?

The idea is that at each round of the BFS, we mark the cells to be visited in the input grid with a specific timestamp.

By round, we mean a snapshot in time where a group of oranges turns rotten.

Algorithm

Grid Snapshot I

Grid Snapshot II

In the above graph, we show how we manipulate the values in the input grid in-place in order to run the BFS traversal.

  • 1). Starting from the beginning (with timestamp=2), the cells that are marked with the value 2 contain rotten oranges. From this moment on, we adopt a rule stating as "the cells that have the value of the current timestamp (i.e. 2) should be visited at this round of BFS.".

  • 2). For each of the cell that is marked with the current timestamp, we then go on to mark its neighbor cells that hold a fresh orange with the next timestamp (i.e. timestamp += 1). This in-place modification serves the same purpose as the queue variable in the previous BFS implementation, which is to select the candidates to visit for the next round.

  • 3). At this moment, we should have timestamp=3, and meanwhile we also have the cells to be visited at this round marked out. We then repeat the above step (2) until there is no more new candidates generated in the step (2) (i.e. the end of BFS traversal).

To summarize, the above algorithm is still a BFS traversal in a 2D grid. But rather than using a queue data structure to keep track of the visiting order, we applied an in-place algorithm to serve the same purpose as a queue in a more classic BFS implementation.

Complexity Analysis

  • Time Complexity: O(N2)\mathcal{O}(N^2) where NN is the size of the input grid.

    In the in-place BFS traversal, for each round of BFS, we would have to iterate through the entire grid.

    The contamination propagates in 4 different directions. If the orange is well adjacent to each other, the chain of propagation would continue until all the oranges turn rotten.

    In the worst case, the rotten and the fresh oranges might be arranged in a way that we would have to run the BFS loop over and over again, which could amount to N2\frac{N}{2} times which is the longest propagation chain that we might have, i.e. the zigzag walk in a 2D grid as shown in the following graph. Grid Zigzag

    As a result, the overall time complexity of the in-place BFS algorithm is O(NN2)=O(N2)\mathcal{O}(N \cdot \frac{N}{2}) = \mathcal{O}(N^2).

  • Space Complexity: O(1)\mathcal{O}(1), the memory usage is constant regardless the size of the input. This is the very point of applying in-place algorithm. Here we trade the time complexity with the space complexity, which is a common scenario in many algorithms.

Report Article Issue

Comments: 42
a_vlad's avatar
Read More

I get everything but the pun... can anyone explain the Graph pun?

52
Show 2 replies
Reply
Share
Report
dhdnr1220's avatar
Read More

How about include at least two rotten oranges in example?

115
Show 5 replies
Reply
Share
Report
isshiassharma's avatar
Read More

The first one is very easy to understand but the implementation in this particular solution is too complicated. There are more straightforward solutions for the first variant. I'll show you one below:

class Solution {
    public int orangesRotting(int[][] grid) {
    if(grid==null || grid.length == 0) return -1;
        
        int count_fresh = 0;
        Queue<Pair<Integer,Integer>> queue = new LinkedList();
        int R = grid.length, C = grid[0].length;
        
        for(int r = 0; r < R; r++)
            for(int c = 0; c < C; c++)
                if(grid[r][c] == 2) queue.offer(new Pair(r,c));
        else if(grid[r][c]==1) count_fresh++;
        
        if(count_fresh==0) return 0;
        
        int count = 0;
        int dirs[][] = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        
        while(!queue.isEmpty()) {
            count++;
            int size = queue.size();        
            for(int i = 0;i<size;i++){
             Pair<Integer,Integer> pair = queue.poll();
                int row = pair.getKey();
                int col = pair.getValue();
               for(int[] dir:dirs){
                int r = row+dir[0];
                   int c = col+dir[1];
                if(r<0 || r>=R || c<0 || c>=C || grid[r][c] == 0 || grid[r][c] == 2) continue;
                
                grid[r][c] = 2;
                   queue.add(new Pair(r,c));
                count_fresh--;
                
               }
            }
        }
      return count_fresh==0?count -1 : -1;
    }
}

18
Show 1 reply
Reply
Share
Report
gdkou90's avatar
Read More

Why is this not a hard problem?

56
Show 9 replies
Reply
Share
Report
carreaza's avatar
Read More

Shouldn't the first solution be N^2? You have to look in every cell of the grid to continue.

13
Show 5 replies
Reply
Share
Report
purplebeth's avatar
Read More

why do we start minutes at -1 instead of 0?

4
Show 2 replies
Reply
Share
Report
TootZ's avatar
Read More

For the second solution , shouldn't it be N3 runtime? matrix search (N2) is repeated N/2 times.

4
Show 2 replies
Reply
Share
Report
tejakunderu's avatar
Read More

I think there is another way to do this in-place with better time complexity by keeping track of newly rotten oranges at each minute. The older rotten oranges will infect whatever is in the neighborhood, and are no longer required. This way, we can repeat the process until we have no newly rotten oranges. This lets us modify the grid in-place. Here's my code in Python.

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        fresh = 0
        rotten = collections.deque([])
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    rotten.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1
                    
        minutes = 0
        if fresh == 0:
            return minutes
        
        while rotten and fresh:
            l = len(rotten)
            while l:
                l -= 1
                i, j = rotten.popleft()
                if i > 0 and grid[i - 1][j] == 1:
                    grid[i - 1][j] = 2
                    rotten.append((i - 1, j))
                    fresh -= 1
                if i < len(grid) - 1 and grid[i + 1][j] == 1:
                    grid[i + 1][j] = 2
                    rotten.append((i + 1, j))
                    fresh -= 1
                if j > 0 and grid[i][j - 1] == 1:
                    grid[i][j - 1] = 2
                    rotten.append((i, j - 1))
                    fresh -= 1
                if j < len(grid[0]) - 1 and grid[i][j + 1] == 1:
                    grid[i][j + 1] = 2
                    rotten.append((i, j + 1))
                    fresh -= 1
            minutes += 1
        return -1 if fresh else minutes    
    

4
Show 1 reply
Reply
Share
Report
bbhatsrinidhi's avatar
Read More

I still dint get why we can't use a DFS in this problem statement? Granted that BFS is intuitive, the recursive nature of this problem statement got me thinking in the DFS way.
Any explanation would be appreciated.

2
Show 4 replies
Reply
Share
Report
ajalbani's avatar
Read More

clean Javascript BFS Solution

/* BFS Solution */
var orangesRotting = function(grid, STATES=Object.freeze({FRESH: 1, ROTTEN:2}), dir=[[-1,0],[0,1],[0,-1],[1,0]]) {
    let q = [], fresh = 0, min = 0;
    for(let x=0; x<grid.length; x++) {
        for(let y=0; y<grid[x].length; y++) {
                 if(grid[x][y]===STATES.ROTTEN) q.push([x, y])
            else if(grid[x][y]===STATES.FRESH)  fresh++;
        }
    }
    while(q.length && fresh) {
        let n = [];
        while(q.length) {
            let [x, y] = q.shift();
            for(let [i, j] of dir) {
                let xN = x+i, yN = y+j; //xN means x Next
                if(grid[xN] !== undefined && grid[xN][yN] !== undefined && grid[xN][yN]===STATES.FRESH) {
                    fresh -= 1;
                    grid[xN][yN] = STATES.ROTTEN;
                    n.push([xN, yN]);
                }
            }
        }
        min++;
        q = n;
    }
    return fresh == 0 ? min : -1;
}

2
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
10/08/2020 08:53Accepted12 ms13 MBcpp
10/08/2020 08:53Compile ErrorN/AN/Acpp
10/08/2020 08:51Accepted8 ms13 MBcpp
08/09/2020 13:34Accepted4 ms12.9 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.